#include <iostream>

namespace {

template<typename T>
void ShellSort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}

template<typename T>
void PrintList(T array[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << array[i] << ",";
    }
    std::cout << std::endl;
}

void shell_sort(int arr[], int len)
{
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)
        for (i = gap; i < len; i++)
        {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

void Handle() {
    int array[] = {8,9,1,7,2,3,5,4,6,0};
    int len = sizeof(array) / sizeof(int);
    PrintList(array, len);
    shell_sort(array, len);
    PrintList(array, len);
}

}

void HandleSort() {
    Handle();
}
